#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	freopen("never.in","r",stdin);
	freopen("never.out","w",stdout);
	int T=read();
	while(T--){
		int a=read(),b=read();
		if(a>b)swap(a,b);
		if(b%a==0)printf("%d\n",b);
		else if(__gcd(a,b)!=1)printf("%d\n",a+b);
		else{
			int res=(a&1?a*2:a)+(b&1?b*2:b);
			int res1=0,res2=0;
			for(int i=2;i*i<=a;i++)if(a%i==0){res1=i;break;}
			if(!res1)res1=a,a=0;
			for(int i=2;i*i<=b;i++)if(b%i==0){res2=i;break;}
			if(!res2)res2=b,b=0;
//			printf("1:%d 2:%d\n",res1,res2);
			res=min(res,a+b+2*((res1==2?0:res1)+(res2==2?0:res2)));
			printf("%d\n",res);
		}
	}
	return 0;
}
